package DataStructure.tree;

import java.util.ArrayDeque;
import java.util.Deque;

//二叉树
public class BinaryTree{
    private Node root;//根节点
    private int size;//节点数量

    private static class Node{
        private char e;
        private Node left;
        private Node right;
        private int h;//以该节点为根的树的高度
        private boolean ltag;//左子节点是否为线索
        private boolean rtag;//右子节点是否为线索
        public Node(char e, Node left, Node right) {
            this.e=e;
            this.left=left;
            this.right=right;
            this.h=1;
            this.ltag=false;
            this.rtag=false;
        }
    }

    public BinaryTree(String pre,String in) {
        root=build(pre,in);
        size=pre.length();
    }

    //由前序遍历和中序遍历构建树
    private Node build(String pre, String in){
        if(pre.equals("")) return null;
        char c=pre.charAt(0);
        Node n= new Node(c, null, null);
        if(in.length()==1) return n;
        String[] ss=in.split(String.valueOf(c));//分割中序串
        n.left=build(pre.substring(1,1+ss[0].length()),ss.length==2?ss[0]:"");
        n.right=build(pre.substring(1+ss[0].length()),ss.length==2?ss[1]:"");
        n.h=Math.max(n.left==null?0:n.left.h,n.right==null?0:n.right.h)+1;
        return n;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size==0;
    }

    public int height() {
        return root==null?0:root.h;
    }

    //先序遍历
    public void preOrder(Node n){
        if(n==null)
            return;
        System.out.println(n.e);
        preOrder(n.left);
        preOrder(n.right);
    }
    //test
    public void preOrder2(){
        Deque<Node> s=new ArrayDeque<>();
        Node n=root;
        while(n!=null||!s.isEmpty()){
            if(n!=null){
                System.out.println(n.e);
                s.add(n);
                n=n.left;
            }else{
                n=s.poll();
                n=n.right;
            }
        }
    }
    //中序遍历
    public void inOrder(Node n){
        if(n==null)
            return;
        inOrder(n.left);
        System.out.println(n.e);
        inOrder(n.right);
    }
    public void inOrder2(){
        Deque<Node> s=new ArrayDeque<>();
        Node n=root;
        while(n!=null||!s.isEmpty()){
            if(n!=null){
                s.add(n);
                n=n.left;
            }else{
                n=s.pollLast();
                System.out.println(n.e);
                n=n.right;
            }
        }
    }
    //后序遍历
    public void postOrder(Node n){
        if(n==null)
            return;
        postOrder(n.left);
        postOrder(n.right);
        System.out.println(n.e);
    }
    public void postOrder2(){
        Deque<Node> s=new ArrayDeque<>();
        Node n=root;
        Node last=null;//判断是否从右子树返回
        while(n!=null||!s.isEmpty()){
            if(n!=null){
                s.add(n);
                n=n.left;
            }else{
                n=s.getFirst();
                if(n.right!=null&&last!=n.right)//访问右子树
                    n=n.right;
                else{//子树全部访问
                    n=s.pollLast();
                    System.out.println(n.e);
                    last=n;
                    n=null;
                }
            }
        }
    }
    //层序遍历
    public void layerOrder(Deque<Node> q){
        if(q.isEmpty()) return;
        Node n=q.poll();
        System.out.println(n.e);
        if(n.left!=null)
            q.add(n.left);
        if(n.right!=null)
            q.add(n.right);
        layerOrder(q);
    }
    public void layerOrder2(){
        Deque<Node> q=new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()){
            Node n= q.poll();
            System.out.println(n.e);
            if(n.left!=null)
                q.add(n.left);
            if(n.right!=null)
                q.add(n.right);
        }
    }

    //中序线索化
    public void inThread(){
        inThread(root,null).rtag=true;
    }
    private Node inThread(Node n, Node pre){
        if(n==null) return pre;
        //线索化左子树,返回最后一个节点
        Node last=inThread(n.left,pre);
        //当前节点的左子节点线索化
        if(n.left==null){
            n.left=pre;
            n.ltag=true;
        }
        //前驱节点的右子节点线索化
        if(last!=null&&last.right==null){
            last.right=n;
            last.rtag=true;
        }
        //线索化右子树,返回最后一个节点
        return inThread(n.right,n);
    }
    //遍历中序线索二叉树
    public void inOrderThread(){
        Node cur=root;//找到第一个节点
        while(!cur.ltag){
            cur=cur.left;
        }
        while(cur!=null){
            System.out.println(cur.e);
            if(!cur.rtag){//找到右子树的第一个节点
                cur=cur.right;
                while(!cur.ltag){
                    cur=cur.left;
                }
            }else cur=cur.right;
        }
    }

    public static void main(String[] args) {
        BinaryTree t=new BinaryTree("abdce","bdaec");
        t.inThread();
        t.inOrderThread();
    }
}
